package com.lihepeng.leecode.classic.bfs;


import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 二叉树的深度优先遍历
 */
public class BFSTravel {
    // 深度优先遍历二叉树
    public String depthFirstSearch(TreeNode node) {
        StringBuffer sb = new StringBuffer();
        Stack<TreeNode> stack = new Stack();
        stack.push(node);
        while (!stack.isEmpty()) {
            TreeNode popNode = stack.pop();
            sb.append(popNode.data);
            sb.append("=>");
            if (popNode.rightChild != null) {
                stack.push(popNode.rightChild);
            }
            if (popNode.leftChild != null) {
                stack.push(popNode.leftChild);
            }
        }
        return sb.toString();

    }

    // 广度优先遍历二叉树
    public String breadFirstSearch(TreeNode node) {
        StringBuffer sb = new StringBuffer();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()) {
            TreeNode treeNode = queue.poll();
            sb.append(treeNode.data);
            sb.append("=>");
            if (treeNode.leftChild != null) {
                queue.offer(treeNode.leftChild);
            }
            if (treeNode.rightChild != null) {
                queue.offer(treeNode.rightChild);
            }

        }
        return sb.toString();

    }

    @Test
    public void runTest() {
        TreeNode treeNode = new TreeNode(0);
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        treeNode.leftChild = node1;
        treeNode.rightChild = node2;
        node1.leftChild = node3;
        node1.rightChild = node4;
        node2.leftChild = node5;
        node2.rightChild = node6;
        String s = this.breadFirstSearch(treeNode);
        String s1 = this.depthFirstSearch(treeNode);
        System.out.println(s);
        System.out.println(s1);

    }
}
